/**
 * 169. 多数元素
 * https://leetcode-cn.com/problems/majority-element/
 */

// /**
//  * @param {number[]} nums
//  * @return {number}
//  */
// function majorityElement(nums) {
//   const cache = [];
//   const half = nums.length >> 1;
//   for (let i = 0; i < nums.length; i += 1) {
//     const num = nums[i];
//     const count = cache[num] || 0;
//     if (count >= half) return num;
//     cache[num] = (count || 0) + 1;
//   }
//   return 0;
// }

/**
 * 摩尔投票法
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
  let count = 0;
  let candidate;
  for (let i = 0; i < nums.length; i += 1) {
    if (count === 0) {
      candidate = nums[i];
    }
    count += (candidate === nums[i] ? 1 : -1);
  }
  return candidate;
}

console.log(majorityElement([3, 2, 3]) === 3);
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]) === 2);
console.log(majorityElement([1]) === 1);
